COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm a69.tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, November 2, 1988}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Standardizing a DPDM}
\medskip
\noindent{\bf Theorem}:  The class of languages accepted by Deterministic Pushdown 
Machine programs is closed under complementation.

\noindent {\bf Proof}.  It suffices to show that every language accepted by a DPDM 
program is accepted by a program for a standardized machine that halts on all 
inputs.

We standardize an arbitrary DPDM program in stages.

\noindent Step 1.  Factor the program so that from each control state, transitions
depend upon at most one non-control device.  This can be accomplished by
introducing tests for each device, and building a decision tree.  In particular,
we can ensure determinism is preserved, and the resulting program accepts the
same language.

{\bf Example}
\vskip 1.5in
is replaced by
\vfill\eject
\noindent Step 2.  Minimize the repertory of each device.  As discussed previously,
({\it Examples of Machine Simulations}), standardize the input to use only 
{\tt scan} operations and a single {\tt eof} test; standardize the stack to use
only {\tt pushes} and {\tt pops}.  It is clear that any standardized program
executes no more than $\mid x\mid + 1$ input operations on input $x$.

\noindent Step 3.  Add a cleanup state that clears all devices and enters a
rejecting halt.
\vskip 1in
\noindent Step 4.  Eliminate inaccessible control states; the resulting set
of control states is 
$$\bigcup↓{x\in\Sigma↑\ast}\lbrack x \circ\alpha↓Q \circ \nu↑\ast ↓Q\rbrack.$$
Eliminate cul-de-sacs, that is, sets of control states that can be entered
but not exited, by replacing all transitions into a cul-de-sac by 
transitions to the cleanup state.

Eliminate by cancellation with {\tt pops}, any {\tt pushes} that lead inexorably  
to {\tt pops} via paths without branches, the only intermediate instructions 
consisting of {\tt noops} and {\tt writes}.

{\bf Example}
\vskip 1in
is replaced by
\vskip 1in
Replace all control states from which no sequence of control operations leads to
an accepting halt, by a rejecting halt.  Optional:  remove {\tt noops}.

We argue that the resulting standardized machine halts on all input strings.
Indeed, suppose there were an infinite computation.  There must be a last
scan (or none at all) and a last eof test.  No other input operations
are used.  If there is a last pop, or none at all, the program eventually
executes only writes, noops, and pushes.  Because these are non-branching,
they would have been replaced by rejecting halts (why?).

If there is a last push, there must be a last pop, or none at all, after which 
there are only writes and noops, which would have been replaced by rejecting halts
as in the previous case
\vfill\eject

In the remaning case, there must be infinitely many pushes and pops.
Choose a push executed after the last input operation.  Find the next pop.  Find
its previous push.  This push-pop pair would have been cancelled, absurd.

We conclude no such infinite computation exists.
\bye